<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>节点查找</title>
</head>
<body>
    
    <script>
        //1、定义一个二叉树的对象
        function BinaryTree() {
            //S1-节点
            var Node = function(key) {
                this.key = key;
                this.left = null;
                this.right = null;
            }
            //S2-根节点
            var root = null;

            //S4-插入节点
            var insertNode = (node,newNode) => {
                //S4-1-当新节点小于本节点，左边插入；
                if(newNode.key < node.key){
                    if(node.left === null){
                        node.left = newNode;
                    }else{
                        insertNode(node.left, newNode);
                    }
                }else{
                    //S4-2-否则，右边插入；
                    if(node.right === null){
                        node.right = newNode;
                    }else{
                        insertNode(node.right, newNode);
                    }

                }
            }

            //S3-插入
            this.insert = (key) => {
                var newNode = new Node(key);
                if(root === null){
                    root = newNode;
                }else {
                    insertNode(root,newNode);
                }
            }
            //S5-1- 中序遍历实现
            var inOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    inOrderTraverseNode(node.left,callback);    // 左
                    callback(node.key);                         // 中
                    inOrderTraverseNode(node.right, callback);  // 右
                }
            }

            //S5-中序遍历节点
            this.inOrderTraverse = (callback) => {
                inOrderTraverseNode(root, callback); // 从根节点遍历；
            }

            //S6-1- 前序遍历实现
            var preOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    callback(node.key);                         // 中
                    preOrderTraverseNode(node.left,callback);    // 左
                    preOrderTraverseNode(node.right, callback);  // 右
                }
            }
            // S7- 后序遍历节点
            this.preOrderTraverse = (callback) => {
                preOrderTraverseNode(root, callback); // 从根节点遍历；
            }

            //S6-1- 后序遍历实现
            var postOrderTraverseNode = (node, callback) => {
                if(node != null) {
                    postOrderTraverseNode(node.left,callback);    // 左
                    postOrderTraverseNode(node.right, callback);  // 右
                    callback(node.key);                         // 中
                }
            }
            // S6- 后序遍历节点
            this.postOrderTraverse = (callback) => {
                postOrderTraverseNode(root, callback); // 从根节点遍历；
            }
            // S7-1 查找最小值 实现，
            var minNode = (node) => {
                if(node) {
                    while ( node && node.left !=null){
                        node = node.left;
                    }
                    return node.key;
                }
                return null;
            }
            // S7- 查找最小值节点
            this.min = () => {
                return minNode(root);
            }
            // S8-1 查找最大值 实现，
            var maxNode = (node) => {
                if(node) {
                    while ( node && node.right !=null){
                        node = node.right;
                    }
                    return node.key;
                }
                return null;
            }
            // S8- 查找最大值
            this.max = () => {
                return maxNode(root);
            }

            // S9-查找实现
            var searchNode = (node,key) => {
                if( node ===null){
                    return false;
                }
                if(key <node.key){
                    return searchNode(node.left, key);
                } else if (key > node.key){
                    return searchNode(node.right, key);
                }else {
                    return true;
                }

            }
            // S9- 查找
            this.search = (key) => {
                return searchNode(root, key);
            }

            // S10-1 找到节点的最小值
            var findMinNode = (node) => {
                if(node){
                    while (node && node.left != null){
                        node = node.left;
                    }
                    return node;
                }
                return null;
            }

            // S10- 删除实现
            var removeNode = (node,key) => {
                if(node === null){
                    return null;
                }

                if(key <node.key){
                    node.left = removeNode(node.left, key);
                    return node;
                } else if (key > node.key) {
                    node.right = removeNode(node.right, key);
                    return node;
                } else {
                    // P-1: 当为叶节点时；
                    if(node.left === null &&node.right === null){
                        node = null;
                        return node;

                        // P2-: 当左节点为空的时候：
                    }else if (node.left === null && node.right != null){
                        node = node.right;
                        return node;

                        // P3-: 当右节点为空的时候：
                    }else if (node.right === null && node.left != null){
                        node = node.left;
                        return node;
                        // P4: 当左右节点都存在时；                  
                    }else{
                        var minNodeSearch = findMinNode(node.right);
                        node.key = minNodeSearch.key;
                        node.right = removeNode(node.right, minNodeSearch.key);
                        return node;
                    }

                }
            }
            
            // S10- 删除
            this.remove = (key) => {
                root = removeNode(root,key);
            }


        }

        var nodes = [8,3,10,1,6,14,4,7,13];
        var binaryTree = new BinaryTree();
        nodes.forEach((key) => {
            binaryTree.insert(key);
        })
        console.log(binaryTree);
    
        var callback = (key) => {
                console.log(key);
        }
        binaryTree.inOrderTraverse(callback);

        binaryTree.preOrderTraverse(callback);

        binaryTree.postOrderTraverse(callback);

        var minVal = binaryTree.min();
        console.log(" min Node is : " + minVal);

        var maxVal = binaryTree.max();
        console.log(" max Node is : " + maxVal);

        var findVal7 = binaryTree.search(7);
        console.log(findVal7?"key 7 is found ":"key  7 is not Found");

        var findVal9 = binaryTree.search(9);
        console.log(findVal9?"key 9 is found ":"key  9 is not Found");

    </script>
</body>
</html>